package com.honeywen.mymvc.leetcode;

import java.util.LinkedList;

/**
 * 143. 重排链表
 * https://leetcode-cn.com/problems/reorder-list/
 * @author wangwei
 * @date 2019/1/24 上午10:43
 */
public class RecordListTest {

    public static void main(String[] args) {

        ListNode n1 = new ListNode(1);
        ListNode n2 = new ListNode(2);
        ListNode n3 = new ListNode(3);
        ListNode n4 = new ListNode(4);
        ListNode n5 = new ListNode(5);
        n1.next = n2;
        n2.next = n3;
        n3.next = n4;
        n4.next = n5;

        print(n1);

        print(reorderList(n1));
        System.out.println();
        print(reorderList2(n1));
        System.out.println();

        recordList3(n1);


    }

    private static void print(ListNode head) {

        if (head == null) {
            return;
        }
        System.out.print(head.val + "->");

        print(head.next);
    }


    public static  void recordList5(ListNode head) {
        ListNode node = head;






    }
    public static  void recordList4(ListNode head) {


        ListNode fast = head;
        ListNode slow = head;

        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }

        // 翻转slow
        ListNode node = slow.next;




    }


    public static  void recordList3(ListNode head) {
        LinkedList<ListNode> queue = new LinkedList<>();
        ListNode cur = head;
        while (cur != null) {
            queue.addLast(cur);
            cur = cur.next;
        }
        while (!queue.isEmpty()) {
            if (cur == null) {
                cur = queue.pollFirst();
            } else {
                cur.next = queue.pollFirst();
                cur = cur.next;
            }
            cur.next = queue.pollLast();
            cur = cur.next;

        }

        if (cur != null) {
            cur.next = null;
        }

        print(cur);

    }

    public static ListNode reorderList2(ListNode head) {

        LinkedList<ListNode> list = new LinkedList<>();

        ListNode node = head;
        while (node != null) {
            list.add(node);
            node = node.next;
        }
        node = list.pollFirst();
        boolean flag = true;
        while (!list.isEmpty()) {
            if (flag) {
                node.next = list.pollLast();
                flag = false;
            } else {
                node.next = list.pollFirst();
                flag = true;

            }
            node = node.next;

        }

        if (node != null) {
            node.next  = null;
        }


        return node;
    }


    public static ListNode reorderList(ListNode head) {

        LinkedList<Integer> list = new LinkedList<>();

        while (head != null) {
            list.add(head.val);
            head = head.next;
        }

        System.out.println();
        System.out.println(list);


        ListNode node = new ListNode(0);
        ListNode n = node;

        while (list.size() > 0) {

            int a = list.pollFirst();
            n.next = new ListNode(a);

            Integer x = list.pollLast();
            if (x == null) {
                n.next.next = null;
            } else {
                n.next.next = new ListNode(x);
            }
            n = n.next.next;

        }

        return node.next;

    }

}
